package main

import (
	"fmt"
)

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

// 查找数组的最大值对应的索引和值
func findMax(arr []int) (int, int) {
	var maxI, maxV int
	for i, v := range arr {
		if v > maxV {
			maxV = v
			maxI = i
		}
	}
	return maxI, maxV
}

// 查找数组的最大值对应的索引
func findMaxIdx(arr []int) int {
	var maxI, maxV int
	for i, v := range arr {
		if v > maxV {
			maxV = v
			maxI = i
		}
	}
	return maxI
}

// @lc code=start
func maxArea0(height []int) int {
	// index, height
	// var list [][]int
	var l int = len(height)
	if l == 2 {
		return min(height[0], height[1])
	}
	// 计算对比
	var max, val int
	for i := 0; i < l-1; i++ {
		if height[i] == 0 {
			continue
		}
		for j := 1; j < l; j++ {
			if height[j] == 0 {
				continue
			}
			val = (j - i) * min(height[i], height[j])
			if val > max {
				max = val
			}
		}
	}
	return max
}

// @lc code=start
func maxArea1(height []int) int {
	// index, height
	// var list [][]int
	var l int = len(height)
	if l == 2 {
		return min(height[0], height[1])
	}
	{
		// filter 掉无效内容
		// 先找到最大值对应的索引 时间复杂度 O(n)
		var maxI int = findMaxIdx(height)
		// 从最大值的索引往两个方向排查, 去掉无效的值
		for i, t := 1, height[0]; i < maxI; i++ {
			if t >= height[i] {
				height[i] = 0
			} else {
				t = height[i]
			}
		}
		for i, t := l-2, height[l-1]; i > maxI; i-- {
			if t >= height[i] {
				height[i] = 0
			} else {
				t = height[i]
			}
		}
	}
	// 计算对比
	var max, val int
	for i := 0; i < l-1; i++ {
		if height[i] == 0 {
			continue
		}
		for j := 1; j < l; j++ {
			if height[j] == 0 {
				continue
			}
			val = (j - i) * min(height[i], height[j])
			if val > max {
				max = val
			}
		}
	}
	return max
}

// @lc code=start
func maxArea2(height []int) int {
	// fmt.Println("\n\nstart \n", height)
	// index, height
	// var list [][]int
	var l int = len(height)
	if l == 2 {
		return min(height[0], height[1])
	}
	// 二维数组, 存放有效数据的 索引 和 值
	var arrDou [][2]int
	var cnt int = 3
	{
		// filter 掉无效内容
		// 先找到最大值对应的索引 时间复杂度 O(n)
		var maxI int = findMaxIdx(height)
		// 从最大值的索引往两个方向排查, 去掉无效的值
		for i, t := 1, height[0]; i < maxI; i++ {
			if t >= height[i] {
				height[i] = 0
			} else {
				t = height[i]
				cnt++
			}
		}
		for i, t := l-2, height[l-1]; i > maxI; i-- {
			if t >= height[i] {
				height[i] = 0
			} else {
				t = height[i]
				cnt++
			}
		}
		// fmt.Println("height \n", height)
		// 二维数组, 存放有效数据的 索引 和 值
		arrDou = make([][2]int, cnt)
		for i, t := 0, 0; i < l; i++ {
			if height[i] > 0 {
				arrDou[t][0] = i
				arrDou[t][1] = height[i]
				t++
			}
		}
	}
	// fmt.Println("arrDou \n", arrDou)

	var mab map[int]int = make(map[int]int)
	// fmt.Println("mab \n", mab)
	// map整合去重
	for i := 0; i < cnt-1; i++ {
		for j := 1; j < cnt; j++ {
			cha := arrDou[j][0] - arrDou[i][0]
			mi := min(arrDou[j][1], arrDou[i][1])
			if cha > mi {
				if cha > mab[mi] {
					mab[mi] = cha
				}
			} else if mi > mab[cha] {
				mab[cha] = mi
			}
		}
	}
	var max, val int
	for k, v := range mab {
		val = k * v
		if val > max {
			max = val
		}
	}
	return max
}

// 两个指针一左一右, 相互往对方移动, 直至重合
// 对于较低的一方来说, 较高的

func maxArea(height []int) int {
	var maxVal, val, line int
	for l, r := 0, len(height)-1; l < r; {
		if height[l] > height[r] {
			line = height[r]
			val = line * (r - l)
			for r--; l < r && height[r] <= line; r-- {
			}
		} else {
			line = height[l]
			val = line * (r - l)
			for l++; l < r && height[l] <= line; l++ {
			}
		}
		if maxVal < val {
			maxVal = val
		}
	}
	return maxVal
}

func main() {
	fmt.Println(maxArea([]int{3846, 7214, 9316, 9869, 2423, 4235, 4921, 5878, 9832, 5302, 4298, 43, 7824, 4386, 3696, 6984, 4126, 5660, 5716, 1124, 4043, 1510, 5650, 9957, 6481, 1193, 7766, 2563}))
	fmt.Println(maxArea([]int{1, 1}))
	fmt.Println(maxArea([]int{4, 3, 2, 1, 4}))
	fmt.Println(maxArea([]int{1, 2, 1}))

}
